# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head:
            return None
        def mergeTwoLists(l1, l2):
            if not l1:
                return l2
            if not l2:
                return l1
            if l1.val>l2.val:
                temp=l2
                l2=l1
                l1=temp
            temp=l1
            while l2:
                while temp.next and l2.val>temp.next.val:
                    temp=temp.next
                record1=temp.next
                record2=l2.next
                temp.next=l2
                l2.next=record1
                l2=record2
            return l1     
        def divide(node):
            fast=slow=node
            while fast and fast.next:
                fast=fast.next.next
                if not fast:
                    break
                slow=slow.next
            sep=slow.next
            slow.next=None
            if not node.next:
                return mergeTwoLists(node,sep)
            else:
                return mergeTwoLists(divide(node),divide(sep))
        return divide(head)

 
#  执行用时：
# 584 ms
# , 在所有 Python3 提交中击败了
# 9.01%
# 的用户
# 内存消耗：
# 29.9 MB
# , 在所有 Python3 提交中击败了
# 81.57%
# 的用户               